package code.classic150on2025;

import java.util.*;

public class TheStack {
    // 71. 简化路径
    public String simplifyPath(String path) {
        Deque<String> stack = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < path.length(); i++) {
            char c = path.charAt(i);
            if (c == '/' && (i > 0 && path.charAt(i - 1) == '/' || i == 0 || i == path.length() - 1))
                continue;
            sb.append(c);
        }
        String s = sb.toString();
        String[] splits = s.split("/");
        for (String split : splits) {
            if (split.equals("..") ) {
                if (!stack.isEmpty())
                    stack.removeLast();
            } else if (!split.equals(".")) {
                stack.addLast(split);
            }
        }
        sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append('/');
            sb.append(stack.removeFirst());
        }
        if (sb.length() == 0)
            sb.append('/');
        return sb.toString();
    }

    static class MinStack {
        Deque<Integer> stack;
        Deque<Integer> min;

        public MinStack() {
            stack = new ArrayDeque<>();
            min = new ArrayDeque<>();
        }

        public void push(int val) {
            stack.push(val);
            if (min.isEmpty()) {
                min.push(val);
            } else {
                min.push(Math.min(min.peek(), val));
            }
        }

        public void pop() {
            stack.pop();
            min.pop();
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return min.peek();
        }
    }

    // 150. 逆波兰表达式求值
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String token : tokens) {
            if (Character.isDigit(token.charAt(0)) || token.charAt(0) == '-' && token.length() > 1) {
                stack.push(Integer.parseInt(token));
            } else {
                int i1 = stack.pop();
                int i2 = stack.pop();
                switch (token) {
                    case "+" -> stack.push(i2 + i1);
                    case "-" -> stack.push(i2 - i1);
                    case "*" -> stack.push(i2 * i1);
                    case "/" -> stack.push(i2 / i1);
                }
            }
        }
        return stack.pop();
    }

    // 224. 基本计算器
    public int calculate(String s) {
        s = s.trim();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == ' ') continue;
            if (i == 0 && c == '-' || i != 0 && c == '-' && sb.charAt(sb.length() - 1) == '(')
                sb.append('0');
            sb.append(c);
        }
        s = sb.toString();
        Deque<Integer> stack_num = new ArrayDeque<>();
        Deque<Character> stack_op = new ArrayDeque<>();
        Map<Character, Integer> map = new HashMap<>();
        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2);
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                int pos = i, num = 0;
                while (pos < s.length() && Character.isDigit(s.charAt(pos))) {
                    num = num * 10 + (s.charAt(pos) - '0');
                    pos++;
                }
                i = pos - 1;
                stack_num.push(num);
            } else if (c == '(') {
                stack_op.push(c);
            } else if (c == ')') {
                while (!stack_op.isEmpty() && stack_op.peek() != '(')
                    calculateOnce(stack_num, stack_op);
                stack_op.pop();
            } else {
                while (!stack_op.isEmpty() && stack_op.peek() != '(' && map.get(c) <= map.get(stack_op.peek()))
                    calculateOnce(stack_num, stack_op);
                stack_op.push(c);
            }
        }
        while (!stack_op.isEmpty())
            calculateOnce(stack_num, stack_op);
        return stack_num.peek();
    }

    private void calculateOnce(Deque<Integer> stack_num, Deque<Character> stack_op) {
        int i1 = stack_num.pop();
        int i2 = stack_num.pop();
        char op = stack_op.pop();
        switch (op) {
            case '+' -> stack_num.push(i2 + i1);
            case '-' -> stack_num.push(i2 - i1);
            case '*' -> stack_num.push(i2 * i1);
            case '/' -> stack_num.push(i2 / i1);
        }
    }

    public static void main(String[] args) {
        TheStack t = new TheStack();
        System.out.println(t.calculate(" 2-1 + 2 "));
    }
}

